import java.util.Stack;

public class OJ {
    public boolean isValid(String s) {
        //申请栈
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            }else {
                if(stack.empty()) {
                    return false;
                }
                if(s.charAt(i) == ')' && stack.peek() == '(' || s.charAt(i) == ']' && stack.peek() == '[' || s.charAt(i) == '}' && stack.peek() =='{') {
                    //当前 左括号 和 右括号匹配
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        if(!stack.empty()) {
            return false;
        }

        return true;
    }


    //逆波兰表达式求值
    /**
     * 法一：栈
     * @param tokens
     * @return
     */
    public int evalRPN1(String[] tokens) {
        //申请栈
        Stack<Integer> stack = new Stack<>();

        //遍历字符串 tokens
        for(String s : tokens) {
            if(!isOperations(s)) { //是数字
                stack.push(Integer.parseInt(s));
            }else { //是运算符,抽出头两个元素运算
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(s) {
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" ://减的时候为字符串前一个减后一个，由栈的先进后出，就是第二个出栈的被减
                        stack.push(num1 - num2);
                        break;
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.peek();
    }
    private boolean isOperations(String s) {
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }


    /**
     * 法二：数组模拟栈
     * @param tokens
     * @return
     */
    public int evalRPN2(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n+1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {//遍历字符串
            String token = tokens[i];//在符号之前至少有2个数字，且每两个数字消耗一个运算符
            switch(token) {
                case "+":
                    index--;
                    stack[index] += stack[index+1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index+1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index+1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index+1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }

    //出栈入栈次序匹配
    /**
     * 法一：辅助栈
     */
    public boolean IsPopOrder1(int[] pushV, int[] popV) {
        int i = 0;
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for (i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //注意 栈可能会空 且 数组可能会越界
            while(!stack.empty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    /**
     * 法二：原地栈
     * @param pushV
     * @param popV
     * @return
     */
    public boolean IsPopOrder2(int[] pushV, int[] popV) {
        //表示栈空间的大小，初始化为0
        int n = 0;
        //出栈序列的下标
        int j = 0;
        //对于每个待入栈的元素
        for(int num : pushV) {
            //加入栈顶
            pushV[n] = num;
            //当栈不为空且栈顶等于当前出栈序列
            while(n >= 0 && pushV[n] == popV[j]) {
                //出栈,缩小栈空间
                j++;
                n--;
            }
            n++;
        }
        //最后的栈是否为空
        return n == 0;
    }

}
